/**
 * 面试题 17.12. BiNode
 * https://leetcode-cn.com/problems/binode-lcci/
 */
public class Solutions_mianshi_17_12 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(1);
        root.left.left.left = new TreeNode(0);
        root.left.right = new TreeNode(3);
        root.right = new TreeNode(5);
        root.right.right = new TreeNode(6);  // output: {0, 1, 2, 3, 4, 5, 6}

        TreeNode result = convertBiNode(root);
        System.out.println(result);
    }

    private static TreeNode head = new TreeNode(-1);
    private static TreeNode pre = null;

    public static TreeNode convertBiNode(TreeNode root) {
        dfs(root);
        return head.right;
    }

    public static void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        // 左中右遍历
        dfs(root.left);
        // pre 为 null 时，说明还没有遍历到二叉搜索树 root 中的最小元素
        if (pre == null) {
            // 记录头结点
            head.right = root;
            pre = root;
        } else {
            // 将当前节点，作为前一节点的右子节点
            pre.right = root;
            pre = pre.right;
        }
        // 每个节点的左子节点置空
        root.left = null;
        dfs(root.right);
    }
}
